package com.shm.leetcode;

import java.util.Arrays;

/**
 * @author: shm
 * @dateTime: 2020/10/16 8:48
 * @description: 977. 有序数组的平方
 * 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
 *
 * 示例 1：
 *
 * 输入：[-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 示例 2：
 *
 * 输入：[-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 *
 * 提示：
 *
 * 1 <= A.length <= 10000
 * -10000 <= A[i] <= 10000
 * A 已按非递减顺序排序。
 */
public class SortedSquares {
    public int[] sortedSquares(int[] A) {
        for (int i = 0; i < A.length; i++) {
            A[i] = A[i]*A[i];
        }
        Arrays.sort(A);
        return  A;
    }

    public int[] sortedSquares_2(int[] A) {
        for (int i = 0; i < A.length; i++) {
            A[i] = Math.abs(A[i]);
        }
        Arrays.sort(A);
        for (int i = 0; i < A.length; i++) {
            A[i] = A[i]*A[i];
        }
        return  A;
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/16 9:07
     * @description: 方法三：双指针
     * 思路与算法
     *
     * 同样地，我们可以使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 AA 的长度。
     *
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
     */
    public int[] sortedSquares_3(int[] A) {
        int[] ans = new int[A.length];
        int len = A.length-1;
        int i = 0,j=A.length-1;
        while (i<=j){
            int start = A[i]*A[i];
            int end = A[j]*A[j];
            if (start>end){
                ans[len] = start;
                i++;
            }else {
                ans[len] = end;
                j--;
            }
            len--;
        }
        return ans;
    }
}
